package leetcode.sword;

class Solution43 {

    public static void main(String[] args) {
        Solution43 ss = new Solution43();
        System.out.println(ss.countDigitOne(12));
    }

//组合数学：计算含有一个1的数，2个1的数，..
//    public int countDigitOne(int n) {
//        //先计算n是多少位数，并得到最高位
//        int dits = 0, highDit = 0;
//        while(n>0){
//            highDit = n % 10;
//            dits ++;
//            n /= 10;
//        }
//        int cout, sum = 0;
//        for(int i=1;i<=dits;i++){//对含有i个1的数字个数进行统计
//            cout = 0;
//            //最高位是1：C(dits-1,i-1) * 9^(dits-i)
//            cout = combination(dits-1,i-1)*myPow(9,dits-i);
//
//            //最高位非1: highDit * C(dits-1,i) * 9^(dits-1-i)
//            cout += highDit*combination(dits-1,i)*myPow(9,dits-1-i);
//
//            //统计
//            sum += cout*i;
//        }
//
//        return sum;
//    }
//
//    public int combination(int n, int m){
//        if(m<1) return 1;
//        int fenzi = 1, fenmu = 1, tmp = m;
//        while(m>0){
//            fenmu *= m;
//            m--;
//        }
//        int n_m = n - tmp;
//        while(n>n_m){
//            fenzi *= n;
//            n --;
//        }
//        return fenzi/fenmu;
//    }
//
//    public int myPow(int n, int m){
//        if(m<0) return 0;
//        return (int) Math.pow(n,m);
//    }

    public int countDigitOne(int n) {
        int low = 0;
        int cur = n%10;
        int high = n/10;
        int digit = 1;
        int sum = 0;
        while (low<n){
            if(cur>1){
                sum += (high+1)*digit;
            }else if(cur==1){
                sum += high*digit + low + 1;
            }else {
                sum += high*digit;
            }
            low += cur*digit;
            cur = high%10;
            high /= 10;
            digit *= 10;
        }
        return sum;
    }
}